package style.zcyLeetCode.a_0007_贪心算法;

import java.util.Comparator;
import java.util.PriorityQueue;

public class IPO {

    public static class Node {
        public int p;  // 利润
        public int c;  // 资本

        public Node(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    /**
     * 小顶堆
     */
    public static class MinCostComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o1.c - o2.c;
        }
    }

    /**
     * 大顶堆
     */
    public static class MaxCostComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o2.c - o1.c;
        }
    }


    /**
     * @param k       最多选多少个项目
     * @param W       初始资金
     * @param Profits 利润
     * @param Capital 资本
     * @return 返回最大利润
     */
    public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        Node[] nodes = new Node[Profits.length];
        for (int i = 0; i < Profits.length; i++) {
            nodes[i] = new Node(Profits[i], Capital[i]);
        }

        PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());  // 最小成本
        PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxCostComparator());// 最大利润

        // 所有的项目扔到被锁池中，花费组织的小
        for (int i = 0; i < nodes.length; i++) {
            minCostQ.add(nodes[i]);
        }

        for (int i = 0; i < k; i++) {
            // 能力所及的项目，全解锁
            // 小顶堆不为空 并且 项目所需的资金小于自己的启动资金
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
                maxProfitQ.add(minCostQ.poll());
            }
            if (maxProfitQ.isEmpty()) {
                return W;
            }
            W += maxProfitQ.poll().p;
        }
        return W;
    }
}
